-- Charles Douglas (cmd0028)
-- Jeff Taylor (jwt0025)
-- CSCI 4430

-- tree parser and printer:  parser assumes lists of sub nodes are separated by commas and ignores space characters

data Tree name trees = 
	Atom name | 
	Tree name [Tree name trees] 
	deriving (Eq,Ord,Read,Show)
	
-- printer function
print_tree :: Tree String t -> String
print_tree (Atom name) = name
print_tree (Tree name trees) = name ++ "("++ (join (map print_tree trees) ", ") ++")"

-- helper function:  joins a list of strings together, separated by 'glue'  similar to python join/php implode
join :: [String] -> String -> String
join (str:strs) glue | (length strs) > 0 = concat [str, glue, (join strs glue)]
join (str:strs) glue = str

-- parser function
parse_tree :: String -> Tree String t
parse_tree (c:cs) = t where
	(t, newcs) = parse_tree_expression (strip_spaces(c:cs))
	
	--parses a single tree
	parse_tree_expression :: String -> (Tree String t, String)
	
	-- simple case:  The expression is an atom
	parse_tree_expression (c:cs) | (name_char c) && (end_of_atom (strip_name (c:cs))) = 
		((Atom (pull_name(c:cs))),(strip_name (c:cs)))	

	-- complex case:  the expression is a tree
	parse_tree_expression (c:cs) | (name_char c) && ((head (strip_name (c:cs))) == '(') =
		((Tree (pull_name(c:cs))) (ts),newcs) where
			(ts, newcs) = parse_tree_list (tail(strip_name (c:cs)))
	
	--parses a list of trees
	parse_tree_list :: String->([Tree String t], String)
	-- end of a list
	parse_tree_list (c:cs) | c==')' = ([],cs)
	-- non end of a list
	parse_tree_list (c:cs) = ((t:ts),cs2) where 
	    (t,cs1)=parse_tree_expression (c:cs)
	    (ts,cs2)=parse_tree_list (strip_leading_comma cs1)
   
	-- returns the name consisting of the first characters of the string
	pull_name :: String->String
	pull_name str = fst(sep_name str)
	
	-- removes the name from the first characters of the string, and returns the rest
	strip_name :: String->String
	strip_name str = snd(sep_name str)
	
	--separates the longest name it can find in the first characters of the string from the rest of the string
	sep_name :: String -> (String, String)
	sep_name st = pull_name_tup ("", st) where
		pull_name_tup :: (String, String) -> (String, String)
		pull_name_tup (name, (c:cs)) | (name_char c) =  pull_name_tup ((name ++ [c]), cs)
		pull_name_tup (name, (c:cs)) = (name, (c:cs))
		pull_name_tup (name, []) = (name, [])

	-- returns true if the character can be used in an identifier
	name_char :: Char -> Bool
	name_char c= case c of
		' ' -> False
		'(' -> False
		')' -> False
		',' -> False
		_   -> True

	-- helper for determining whether we've reached the end of a tree identifier or an atom identifier.
	end_of_atom :: String -> Bool
	end_of_atom [] = True
	end_of_atom (c:cs) = case c of
		',' -> True
		')' -> True
		_   -> False
		
	strip_spaces :: String -> String
	strip_spaces st = filter (\x->not(x == ' ')) st
	
	strip_leading_comma :: String->String
	strip_leading_comma [] = []
	strip_leading_comma (c:cs) = if (c == ',') then cs else (c:cs)

-- here is some test data	
test1 = "atom"
test2 = "tree(atom, atom)"
test3 = "tree(tree(atom, atom), atom, tree(atom, atom))"